#pragma once
#ifndef ISPRIME_H
#define ISPRIME_H

#include <iostream>
#include <cmath>

using ll = long long;
static constexpr int MAX = 1005;
bool is_prime[MAX];
int prime[MAX];
int n;
//这是一个判断质数的函数
/*
    1、试除法                    
    2、试除法 优化                 
    3、埃式筛                      
    4、埃式筛优化：欧拉筛（线性筛）   
 */

// 试除法
bool isPrime1(int num)
{
    if (num < 2) return false;
    for (int i = 2; i < num; i++)
        if (num % i == 0) return false;
    return true;
}

// 试除法（优化）
bool isPrime2(int num)
{
    if (num < 2) return false;
    for (int i = 2; i <= sqrt(num); i++)
        if (num % i == 0) return false;
    return true;
}

// 埃式筛
int eshi(int x)
{
    int p = 0;
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[0] = 0;
    is_prime[1] = 0;
    for (int i = 2; i <= x; i++)
        if (is_prime[i])
        {
            prime[++p] = i;
            for (ll j = i * i; j <= x; j += i)
             is_prime[j] = 0;
        }
    return p;
}

// 欧拉筛（线性筛）
int Euler(int n)
{
    int p = 0;
    memset(is_prime, 1, sizeof(is_prime));
    for (int i = 2; i <= n; i++)
    {
        if (is_prime[i]) prime[p++] = i;
        for (int j = 0; j < p, i * prime[j] <= n; j++)
        {
            is_prime[i * prime[j]] = 0;
            if (i % prime[j] == 0) break;
        }
    }
    return p;
}



#endif